#include "data_utils.h"

// sort everything inbetween `low' <-> `high'
void quicksort_uint8(uint8_t arr[], uint8_t low, uint8_t high) {
	uint8_t i = low;
	uint8_t j = high;
	uint8_t y = 0;

	// compare value
	uint8_t z = arr[(low + high) / 2];

	// partition
	do {
		// find member above
		while (arr[i] < z)
			i++;

		/* find element below  */
		while (arr[j] > z)
			j--;

		if (i <= j) {
			// swap two elements
			y = arr[i];
			arr[i] = arr[j];
			arr[j] = y;
			i++;
			j--;
		}
	} while (i <= j);

	//recurse
	if (low < j)
		quicksort_uint8(arr, low, j);

	if (i < high)
		quicksort_uint8(arr, i, high);
}

void quicksort_uint16(uint16_t arr[], uint8_t low, uint8_t high) {
	uint8_t i = low;
	uint8_t j = high;
	uint8_t y = 0;

	// compare value
	uint16_t z = arr[(low + high) / 2];

	// partition
	do {
		// find member above
		while (arr[i] < z)
			i++;

		/* find element below  */
		while (arr[j] > z)
			j--;

		if (i <= j) {
			// swap two elements
			y = arr[i];
			arr[i] = arr[j];
			arr[j] = y;
			i++;
			j--;
		}
	} while (i <= j);

	//recurse
	if (low < j)
		quicksort_uint16(arr, low, j);

	if (i < high)
		quicksort_uint16(arr, i, high);
}



void q_sort8(uint8_t numbers[], uint8_t left, uint8_t right)
{
	uint8_t pivot, l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort8(numbers, left, pivot-1);
  if (right > pivot)
    q_sort8(numbers, pivot+1, right);
}

void q_sort16(uint16_t numbers[], uint8_t left, uint8_t right)
{
	uint16_t pivot;
	uint8_t l_hold, r_hold;

  l_hold = left;
  r_hold = right;
  pivot = numbers[left];
  while (left < right)
  {
    while ((numbers[right] >= pivot) && (left < right))
      right--;
    if (left != right)
    {
      numbers[left] = numbers[right];
      left++;
    }
    while ((numbers[left] <= pivot) && (left < right))
      left++;
    if (left != right)
    {
      numbers[right] = numbers[left];
      right--;
    }
  }
  numbers[left] = pivot;
  pivot = left;
  left = l_hold;
  right = r_hold;
  if (left < pivot)
    q_sort16(numbers, left, pivot-1);
  if (right > pivot)
    q_sort16(numbers, pivot+1, right);
}
